package com.fzy.leetcodeExam.test340;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        //0,1,1,3,
        //8,9,1,5,4,3,6,4,3,7       4
        System.out.println(test.minimizeMax(new int[]{0,1,1,3}, 2));
    }


    public int diagonalPrime(int[][] nums) {

        int n = nums.length;

        Set<Integer> set = new TreeSet<>();

        for(int i = 0;i<n;i++){
            set.add(nums[i][i]);
        }

        for(int i = n-1;i>=0;i--){
            set.add(nums[i][n-i-1]);
        }
        int max = 0;
        for(int val : set){
            if(isPrime(val)){
                if(max < val){
                    max = val;
                }
            }
        }

        return max;
    }
    private boolean isPrime(int val){
        if(val <= 3){
            return val>1;
        }

        int sqrt = (int) Math.sqrt(val);
        for(int i = 3;i<=sqrt;i+=2){
            if(val%2 == 0 || val%i == 0){
                return false;
            }
        }
        return true;
    }


    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] arr = new long[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayList<>());
            }
            map.get(nums[i]).add(i);
        }
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.get(nums[i]);
            int sum = 0;
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j) != i) {
                    sum += Math.abs(list.get(j) - i);
                }
            }
            arr[i] = sum;
        }
        return arr;
    }



    public int minimizeMax(int[] nums, int p) {

        Arrays.sort(nums);

        Set<Integer> set = new HashSet<>();

        for(int i = 0;i<nums.length;i++){

            if(set.contains(nums[i])){
               set.remove(nums[i]);
               p--;
               if(p == 0){
                   return 0;
               }
            }else {
                set.add(nums[i]);
            }
        }

        int len = set.size();
        int[] arr = new int[len];
        int i = 0;
        for(int val : set){
            arr[i] = val;
            i++;
        }

        int ans = 0;
        Arrays.sort(arr);
        List<Integer> list = new LinkedList<>();
        for(int val : arr){
            list.add(val);
        }
        int[] temp = new int[list.size()-1];

        for(int j = 1;j<list.size();j++){
            temp[j-1] = Math.abs(list.get(j)-list.get(j-1));
        }
        Arrays.sort(temp);
        int k = 0;
        for(int j = 0;j<p;j++){
            ans = Math.max(ans,temp[k]);
            k++;
        }
        return ans;

    }
}
